package com.captain.special.二叉树.中等;

import com.captain.leetcode.TreeNode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Des:
 *
 * @author XL
 * @Date 2022/5/16 14:55
 */
public class 从中序与后序遍历序列构造二叉树106 {

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return recur(inorder, postorder);
    }

    public TreeNode recur(int[] in, int[] post) {
        if (in.length == 0 || post.length == 0) {
            return null;
        }
        //12456
        int nodeVal = post[post.length - 1];
        TreeNode node = new TreeNode(nodeVal);
        for (int i = 0; i < in.length; i++) {
            if (in[i] == nodeVal) {
                int[] inLeft = Arrays.copyOfRange(in, 0, i);
                int[] intRight = Arrays.copyOfRange(in, i + 1, in.length);
                int[] postLeft = Arrays.copyOfRange(post, 0, i);
                int[] postRight = Arrays.copyOfRange(post, i, post.length - 1);
                node.left = recur(inLeft, postLeft);
                node.right = recur(intRight, postRight);
                break;
            }
        }
        return node;
    }
}
